import collections
import copy
from typing import List

import numpy as np


#逻辑不是很复杂的逻辑 但是题目的输入输出实在是不好进行可视化 也就不好发现问题到底出现在了哪里
#尝试迭代一次代码 把代码的逻辑理清楚

class Solution:
    def containVirus(self, grid: List[List[int]]) -> int:
        ROW = len(grid)
        COL = len(grid[0])

        res = 0
        wall_built = [[False] * COL for _ in range(ROW)]

        def neighbor(r, c):
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < ROW and 0 <= nc < COL:
                    yield nr, nc

        def BFS(r, c, vis):  # 返回 1。威胁感染区域数量（即墙的数量）， 2。需要建墙的坐标
            # vis是单次在全局搜索连通域使用的标志
            # vis = [ [False]*COL for _ in range(ROW) ]

            # if wall_built[r][c] == True:
            #     return (0, [])

            wall_num = 0
            wall = []
            threaten = set()
            queue = collections.deque()
            queue.append((r, c))
            vis[r][c] = True

            while queue:
                r, c = queue.popleft()

                if wall_built[r][c] == True:  # 建过墙了 阻断了传播途径 也阻断了连通块
                    continue

                for nr, nc in neighbor(r, c):
                    if grid[nr][nc] == 1 and vis[nr][nc] == False:  # 当前时刻下连通的感染区域 遍历
                        queue.append((nr, nc))
                        vis[nr][nc] = True

                    elif grid[nr][nc] == 0:
                        wall_num += 1
                        threaten.add( (nr, nc) )

                wall.append((r, c))

            return (wall_num, wall, len(threaten))

        grid_view = copy.deepcopy(grid)
        grid_view = np.array(grid_view).astype('str')
        print( grid_view )  ###test
        while True:
            #####
            # 单次循环
            vis = [[False] * COL for _ in range(ROW)]
            cur_connect = []
            for r, row in enumerate(grid):
                for c, n in enumerate(row):
                    if n == 1 and vis[r][c] == False:
                        cur_connect.append(BFS(r, c, vis))

            #print([ (n, len(walls) ) for n, walls in cur_connect ] )
            if len(cur_connect) == 0:  # 根本没有感染区
                break

            wall_num, wall, threatenNum = max(cur_connect, key=lambda x: x[2] )
            ##问题就在这个最大的选取 到底是选什么最大的？ 不是建的墙数 也不是病毒的区域面积 而是病毒可能威胁的面积 操 恶心人
            res += wall_num
            for r, c in wall:
                wall_built[r][c] = True
                grid_view[r][c] = '|'
            print('build wall:\n', grid_view)
            print('wall num:{0}\n'.format(res))

            # 感染区扩散
            spread = []
            for r, row in enumerate(grid):
                for c, n in enumerate(row):
                    if grid[r][c] == 1 and wall_built[r][c] == False:
                        for nr, nc in neighbor(r, c):
                            if grid[nr][nc] == 0:
                                spread.append((nr, nc))

            if len(spread) == 0: break

            for nr, nc in spread:
                grid[nr][nc] = 1
                grid_view[nr][nc] = '<'

            print('spread:\n', grid_view )###test
        return res


input_data = [[0,1,0,1,1,1,1,1,1,0],[0,0,0,1,0,0,0,0,0,0],[0,0,1,1,1,0,0,0,1,0],[0,0,0,1,1,0,0,1,1,0],[0,1,0,0,1,0,1,1,0,1],[0,0,0,1,0,1,0,1,1,1],[0,1,0,0,1,0,0,1,1,0],[0,1,0,1,0,0,0,1,1,0],[0,1,1,0,0,1,1,0,0,1],[1,0,1,1,0,1,0,1,0,1]]
print(Solution().containVirus(input_data))